package com.zt.algorithm.sort;

public class QuickSort {
    public static void main(String args[]){
        QuickSort sort = new QuickSort();
        int a[] = new int[]{5,7,1,8,4};
        sort.quickSort(a,0,a.length-1);
        for (int m: a) {
            System.out.println(m);
        }
    }
    public void quickSort(int a[],int left,int right){
        //对a[low..high]快速排序
        int pivotpos;//划分后的基准记录的位置
        if(left < right){//仅当区间长度大于1时才须排序
            pivotpos = Partition(a,left,right);//对a[low..high]做划分
            quickSort(a,left,pivotpos -1);//对左区间递归排序
            quickSort(a,pivotpos + 1,right);//对右区间递归排序
        }
    }
    public int Partition(int a[],int i,int j){
        //调用Partition(a，low，high)时，对a[low..high]做划分，
        //并返回基准记录的位置
        int pivot = a[i];//用区间的第1个记录作为基准
        while (i<j){//从区间两端交替向中间扫描，直至i=j为止
            while (i < j && a[j] >= pivot){//pivot相当于在位置i上
                j--; //从右向左扫描，查找第1个关键字小于pivot的记录R[j]
            }
            if(i < j)//表示找到的a[j]的关键字<pivot
                a[i++] = a[j];//相当于交换a[i]和a[j]，交换后i指针加1
            while (i < j && a[i] <= pivot){//pivot相当于在位置j上
                i++; //从左向右扫描，查找第1个关键字大于pivot的记录a[i]
            }
            if(i <j) //表示找到了a[i]，使a[i].key>pivot
                a[j--] = a[i]; //相当于交换a[i]和a[j]，交换后j指针减1
        }
        a[i] = pivot; //基准记录已被最后定位
        return  i;
    }
}
